

//////////////////////////// Goband Chess ///////////////////////////

/////////////////////    Written by Guo, 2006 ///////////////////////

///////////////////    All rights reserved      ////////////////////

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

int grid[20][20];

struct grid_point {
        int x;
        int y;
};


struct score_combine {
        grid_point single_grid;
        int score;
}; 

vector<score_combine> score_list;
vector<score_combine> score_list2;
int map_band[100];

score_combine scan_grid(const int);
void       evaluate(const grid_point, const int);
void       get_score_store(const grid_point, const int);
int        check_4(const int, const int);
int        check_double_cross(const int, const int);
int        check_who_win(const grid_point);
void       show_current();
void       addto_score_list(const int, const int, const int, const int);
void       flip_the_matrix();
inline bool operator < (const score_combine&, const score_combine&);
inline bool operator == (const grid_point&, const grid_point&);
void       search_in_score_list(const vector<score_combine>::iterator);

int main()
{
        int x,y;
        grid_point next_grid;
        score_combine test_position1;
        score_combine test_position2;
        grid_point response_position;
        grid_point tmp_grid;
        
        for(int i=0; i<20; i++)
        for(int j=0; j<20; j++)
                grid[i][j]=0;

        while(1)
        {
        cout<<"Put your chess, coordinate of X(from 0 to 19):"<<endl;
        cin>>x;
        cout<<"coordinate of Y(from 0 to 19): "<<endl;
        cin>>y;

        while(grid[x][y]!=0)
        {
                cout<<"Sorry, this place has already been filled"<<endl;
                cout<<"Put your chess, coordinate of X(from 0):"<<endl;
                cin>>x;
                cout<<"coordinate of Y(from 0): "<<endl;
                cin>>y;
        }

        grid[x][y]=1;
        tmp_grid.x=x;
        tmp_grid.y=y;

        if(check_who_win(tmp_grid))
        {
                cout<<"Congratulations, You Win!"<<endl;
                return 0;
        }
        
        // 1 is the normal matrix, 2 is the reversed order, that is 1==> -2  && -2 ==> 1

        // in fact test_position1 here is garbage

        test_position1=scan_grid(1);
        flip_the_matrix();
        test_position2=scan_grid(2);
        flip_the_matrix();
        
        response_position=test_position2.single_grid;


        grid[response_position.x][response_position.y]=-2;
        score_list.clear();
        score_list2.clear();

        cout<<"The computer put the chess at: x="<< response_position.x<<"\t y="<<response_position.y<<endl;
        show_current();
        if(check_who_win(response_position))
        {
                cout<<"Sorry, You lost!"<<endl;
                return 0;
        }
        }
        return 0;

}

score_combine scan_grid(const int type)
{
        grid_point next_grid;
        score_combine max_ele;
        int highest_score;
        grid_point highest_score_grid;
        int start_flag=0;
        vector<score_combine>::iterator count;
        int total_high=0;
        int tmp_value=0;
        int tmp_index=0;
        int signal_i, signal_j;

        for(int i=0; i<20; i++)
        for(int j=0; j<20; j++)
        {
                if(grid[i][j]==1)
                {
                        next_grid.x=i;
                        next_grid.y=j;
                        evaluate(next_grid, type); 
                        start_flag=1;
                }
        }

        if(start_flag==0)
        {
                score_list2.push_back(score_list.back());       
        }

        if(type==1)
        {
                highest_score=score_list.back().score;
                highest_score_grid=score_list.back().single_grid;
        }
        else
        {
                highest_score=score_list2.back().score;
                highest_score_grid=score_list2.back().single_grid;
                count=score_list2.end();
                while(highest_score==(*(--count)).score)
                        total_high++;
                // not degenerate
                if(total_high!=1)
                {
                        search_in_score_list(++count);
                        // just find the largest according to map_band
                        for(int i=0; i<total_high; i++)
                        {
                                if(tmp_value<map_band[i])
                                {
                                        tmp_value=map_band[i];
                                        tmp_index=i;
                                }
                        }
                        highest_score=score_list2[score_list2.size()-total_high+tmp_index].score;
                        highest_score_grid=score_list2[score_list2.size()-total_high+tmp_index].single_grid;
                                
                }

                // i do all the process instead of implementation in the main program


        // miss if to tune the software
                if(score_list.back().score-highest_score>=2)
                {

                                // notice that if mpa_band[0]=0 then total_high=1
                                // first need to get the number of maximum score_list members
                                total_high=0;
                                count=score_list.end();
                                highest_score=score_list.back().score;
                                highest_score_grid=score_list.back().single_grid;
                                while(highest_score==(*(--count)).score)
                                        total_high++;
                                for(int j=0; j<score_list2.size(); j++)
                                for(int i=0; i<total_high; i++)
                                {
                                        signal_i=i;
                                        signal_j=j;
                                        if(score_list[score_list.size()-1-i].single_grid==score_list2[score_list2.size()-1-j].single_grid)
                                        {
                                                highest_score=score_list[score_list.size()-1-i].score;
                                                highest_score_grid=score_list[score_list.size()-1-i].single_grid;
                                                break;
                                        }
                                }

                                // if nothing happens, then just do as originally
                                if(signal_i==score_list.size()-1 && signal_j==total_high-1)
                                {
                                        highest_score=score_list.back().score;
                                        highest_score_grid=score_list.back().single_grid;
                                }
                 }      
        

                
        }

        max_ele.score=highest_score;
        max_ele.single_grid=highest_score_grid;
        return max_ele;
}

void evaluate(const grid_point next_grid, const int type)
{
        int now_score=0;
        int last_score=0;
        int now_direction;
        score_combine sing_ele;

        // 3,4,5,6 stands for horizonal, vertical, slash(/), back_slash(\)    

///////////////////////////////////////////// need to be revised
                
                get_score_store(next_grid, type);
        if(type==1)
                sort(score_list.begin(), score_list.end());
        else
                sort(score_list2.begin(), score_list2.end());

/////////////////////////////////////////////
}

void get_score_store(const grid_point next_grid, const int type)
{
        grid_point neighbor=next_grid;
        int left=0;
        int score=0;
        
        for(int direction=3; direction<7; direction++)
        {
        left=0;
        score=0;
        neighbor=next_grid;
        switch(direction) {
                case 3:
                        while (grid[--neighbor.x][neighbor.y]==1);
                        score+=grid[neighbor.x][neighbor.y];
                        left=++neighbor.x;
                        while (grid[++neighbor.x][neighbor.y]==1);
                        score+=neighbor.x-left+grid[neighbor.x][neighbor.y]+30*check_4(neighbor.x, left);
                        // first the left then the right
                        addto_score_list(left-1, neighbor.y, score, type);
                        addto_score_list(neighbor.x, neighbor.y, score, type);
                        break;
                case 4:
                        while (grid[neighbor.x][--neighbor.y]==1);
                        score+=grid[neighbor.x][neighbor.y];
                        left=++neighbor.y;
                        while (grid[neighbor.x][++neighbor.y]==1);
                        score+=neighbor.y-left+grid[neighbor.x][neighbor.y]+30*check_4(neighbor.y, left);
                        addto_score_list(neighbor.x, left-1, score, type);
                        addto_score_list(neighbor.x, neighbor.y, score, type);
                        break;
                case 5:
                        while (grid[--neighbor.x][++neighbor.y]==1);
                        score+=grid[neighbor.x][neighbor.y];
                        left=++neighbor.x;
                        neighbor.y--;
                        while (grid[++neighbor.x][--neighbor.y]==1);
                        score+=neighbor.x-left+grid[neighbor.x][neighbor.y]+30*check_4(neighbor.x, left);
                        addto_score_list(left-1, neighbor.y+(neighbor.x-left+1), score, type);
                        addto_score_list(neighbor.x, neighbor.y, score, type);
                        break;
                case 6:
                        while (grid[--neighbor.x][--neighbor.y]==1);
                        score+=grid[neighbor.x][neighbor.y];
                        left=++neighbor.x;
                        neighbor.y++;
                        while (grid[++neighbor.x][++neighbor.y]==1);
                        score+=neighbor.x-left+grid[neighbor.x][neighbor.y]+30*check_4(neighbor.x, left);
                        addto_score_list(left-1, neighbor.y-(neighbor.x-left+1), score, type);
                        addto_score_list(neighbor.x, neighbor.y, score, type);
        }
        }
}

int check_4(const int a, const int b)
{
        if((a-b)==4)
        return 1;
        else
        return 0;
}

int check_who_win(const grid_point check_point)
{
        int value_of_chk;
        grid_point tmp_grid=check_point;
        int count=1;
        int left;
        value_of_chk=grid[check_point.x][check_point.y];
        // first check horizontal
        while (grid[--tmp_grid.x][tmp_grid.y]==value_of_chk);
        left=++tmp_grid.x;
        while (grid[++tmp_grid.x][tmp_grid.y]==value_of_chk);
        if(tmp_grid.x-left==5)
        return 1;
        // then check vertical
        tmp_grid=check_point;
        while (grid[tmp_grid.x][--tmp_grid.y]==value_of_chk);
        left=++tmp_grid.y;
        while (grid[tmp_grid.x][++tmp_grid.y]==value_of_chk);
        if(tmp_grid.y-left==5)
        return 1;
        // then check backslash(\)
        tmp_grid=check_point;
        while (grid[--tmp_grid.x][++tmp_grid.y]==value_of_chk);
        left=++tmp_grid.x;
        --tmp_grid.y;
        while (grid[++tmp_grid.x][--tmp_grid.y]==value_of_chk);
        if(tmp_grid.x-left==5)
        return 1;
        // last check slash(/)
        tmp_grid=check_point;
        while (grid[--tmp_grid.x][--tmp_grid.y]==value_of_chk);
        left=++tmp_grid.x;
        ++tmp_grid.y;
        while (grid[++tmp_grid.x][++tmp_grid.y]==value_of_chk);
        if(tmp_grid.x-left==5)
                return 1;
        else
                return 0;
}

void show_current()
{
        cout<<"||||||||||||||||||||||||"<<endl;
        cout<<"The Human Player use *"<<endl;
        cout<<"Computer using o"<<endl;
        cout<<"||||||||||||||||||||||||"<<endl;
        cout<<endl;
        cout<<"|-----> Y"<<endl;
        cout<<"|"<<endl;
        cout<<"|"<<endl;
        cout<<"V"<<endl;
        cout<<" "<<endl;
        cout<<"X"<<endl;
        cout<<endl;
        cout<<"   ";
        for(int i=0; i<20; i++)
        {
                if(i<10)
                cout<<' '<<i;
                else
                cout<<i;
        }
        cout<<endl;

        for(int i=0; i<20; i++)
        {
                if(i<10)
                cout<<i<<"  ";
                else
                cout<<i<<' ';
        for(int j=0; j<20; j++)
        {
                if(grid[i][j]==0)
                        cout<<"-|";
                else
                {
                        if(grid[i][j]==1)
                                cout<<"-*";
                        else
                        {
                                if(grid[i][j]==-2)
                                cout<<"-o";
                        }
                } 
        }       
        cout<<endl;
        }
}

void addto_score_list(const int inputx, const int inputy, const int score, const int type)
{
        // travel along the score list so that each duplicate item is plused
        // If no record is in(means it is a new item), create a new one

        score_combine tmp_grid;
if(type==1)
{
        for(int i=0; i<score_list.size(); i++)
        {
                if(score_list[i].single_grid.x==inputx && score_list[i].single_grid.y==inputy)
                {
                        score_list[i].score+=score;
                        return;
                }
        }
        // check if the position is already sit by a enemy chess, 
        // if yes, then assign a large negative value and plus the score, or else just assign the score value 

        if(grid[inputx][inputy]==-2)
        {
                tmp_grid.score=-500;
        }
        else
        {
                tmp_grid.score=0;
                // check whether exists a so-called double cross case
                // to avoid simple traps
                if(check_double_cross(inputx, inputy))
                {
                        tmp_grid.score+=20;
                }
        }
                tmp_grid.score+=score;
                tmp_grid.single_grid.x=inputx;
                tmp_grid.single_grid.y=inputy;
                score_list.push_back(tmp_grid);
}
else
{
        for(int i=0; i<score_list2.size(); i++)
        {
                if(score_list2[i].single_grid.x==inputx && score_list2[i].single_grid.y==inputy)
                {
                        score_list2[i].score+=score;
                        return;
                }
        }
        // check if the position is already sit by a enemy chess, 
        // if yes, then assign a large negative value and plus the score, or else just assign the score value 

        if(grid[inputx][inputy]==-2)
        {
                tmp_grid.score=-500;
        }
        else
        {
                tmp_grid.score=0;
        }
                tmp_grid.score+=score;
                tmp_grid.single_grid.x=inputx;
                tmp_grid.single_grid.y=inputy;
                score_list2.push_back(tmp_grid);
}
                return;
}

inline bool operator<(const score_combine& first, const score_combine& second)
{
        return first.score<second.score;
}

void flip_the_matrix()
{
        for(int i=0; i<20; i++)
        for(int j=0; j<20; j++)
        {
                if(grid[i][j]==1)
                {
                        grid[i][j]=-2;
                }
                else
                {
                        if(grid[i][j]==-2)
                        grid[i][j]=1;
                }
        }
}

void search_in_score_list(const vector<score_combine>::iterator signator)
{
        vector<score_combine>::iterator std_signator=signator;
        vector<score_combine>::iterator comp_signator;
        int top;
        int counter=0;

        for(int i=0; i<100; i++)
        {
                map_band[i]=0;
        }


        for(; std_signator!=score_list2.end(); std_signator++)
        {
        top=score_list.size();
        comp_signator=score_list.end();
                while(--comp_signator!=score_list.begin())
                {
                        if((*(std_signator)).single_grid==(*comp_signator).single_grid)
                        {
                                map_band[counter++]=top;
                                break;
                        }
                        top--;
                }
        }
}

inline bool operator == (const grid_point& first, const grid_point& second)
{
        return (first.x==second.x)&&(first.y==second.y);
}

int check_double_cross(const int inputx, const int inputy)
{
        // first check middle, it must be the following type:
        //      111
        //       111
        //     111
        //    1101
        //       1011
        //    note: it's symmetric according to the middle '1'     
        //    such pattern should appear twice or more
        
        // check four direction 

        int direction[4];
        int total=0;

        direction[0]=0;
        direction[1]=0;
        direction[2]=0;
        direction[3]=0;

        int count=0;

                        if(grid[inputx-1][inputy]==1 && grid[inputx+1][inputy]==1)
                                count=1;
                        if(grid[inputx+1][inputy]==1 && grid[inputx+2][inputy]==1)
                                count=2;
                        if(grid[inputx-2][inputy]==1 && grid[inputx-1][inputy]==1)
                                count=3;
                        if(grid[inputx-3][inputy]==1 && grid[inputx-2][inputy]==1 && grid[inputx-1][inputy]==0)
                                count=4;
                        if(grid[inputx+1][inputy]==0 && grid[inputx+2][inputy]==1 && grid[inputx+3][inputy]==1)
                                count=5;

                        if(count!=0)
                        {
                                direction[0]=count;
                                count=0;
                        }

                        if(grid[inputx][inputy-1]==1 && grid[inputx][inputy+1]==1)
                                count=1;
                        if(grid[inputx][inputy+1]==1 && grid[inputx][inputy+2]==1)
                                count=2;
                        if(grid[inputx][inputy-2]==1 && grid[inputx][inputy-1]==1)
                                count=3;
                        if(grid[inputx][inputy-3]==1 && grid[inputx][inputy-2]==1 && grid[inputx][inputy-1]==0)
                                count=4;
                        if(grid[inputx][inputy+1]==0 && grid[inputx][inputy+2]==1 && grid[inputx][inputy+3]==1)
                                count=5;
                        
                        if(count!=0)
                        {
                                direction[1]=count;
                                count=0;
                        }

                        if(grid[inputx-1][inputy-1]==1 && grid[inputx+1][inputy+1]==1)
                                count=1;
                        if(grid[inputx+1][inputy+1]==1 && grid[inputx+2][inputy+2]==1)
                                count=2;
                        if(grid[inputx-2][inputy-2]==1 && grid[inputx-1][inputy-1]==1)
                                count=3;
                        if(grid[inputx-3][inputy-3]==1 && grid[inputx-2][inputy-2]==1 && grid[inputx-1][inputy-1]==0)
                                count=4;
                        if(grid[inputx+1][inputy+1]==0 && grid[inputx+2][inputy+2]==1 && grid[inputx+3][inputy+3]==1)
                                count=5;

                        if(count!=0)
                        {
                                direction[2]=count;
                                count=0;
                        }

                        if(grid[inputx-1][inputy+1]==1 && grid[inputx+1][inputy-1]==1)
                                count=1;
                        if(grid[inputx+1][inputy-1]==1 && grid[inputx+2][inputy-2]==1)
                                count=2;
                        if(grid[inputx-2][inputy+2]==1 && grid[inputx-1][inputy+1]==1)
                                count=3;
                        if(grid[inputx-3][inputy+3]==1 && grid[inputx-2][inputy+2]==1 && grid[inputx-1][inputy+1]==0)
                                count=4;
                        if(grid[inputx+1][inputy-1]==0 && grid[inputx+2][inputy-2]==1 && grid[inputx+3][inputy-3]==1)
                                count=5;
                        
                        if(count!=0)
                        {
                                direction[3]=count;
                                count=0;
                        }

                        total=direction[0]+direction[1]+direction[2]+direction[3];

                        for(int i=0; i<4; i++)
                        {
                                if(direction[i]!=0 && total==direction[i])
                                        return 0;
                        }
                        
                        if(total!=0)
                        {
                                total=0;
                                for(int i=0; i<4; i++)
                                {
                                switch(direction[i]) {
                                case 1:
                                        if(i==0)
                                                total+=grid[inputx-2][inputy]+grid[inputx+2][inputy];
                                        if(i==1)
                                                total+=grid[inputx][inputy-2]+grid[inputx][inputy+2];
                                        if(i==2)
                                                total+=grid[inputx-2][inputy-2]+grid[inputx+2][inputy+2];
                                        if(i==3)
                                                total+=grid[inputx-2][inputy+2]+grid[inputx+2][inputy-2];
                                        break;  
                                case 2:
                                        if(i==0)
                                                total+=grid[inputx-1][inputy]+grid[inputx+3][inputy];
                                        if(i==1)
                                                total+=grid[inputx][inputy-1]+grid[inputx][inputy+3];
                                        if(i==2)
                                                total+=grid[inputx-1][inputy-1]+grid[inputx+3][inputy+3];
                                        if(i==3)
                                                total+=grid[inputx-1][inputy+1]+grid[inputx+3][inputy-3];
                                        break;  
                                case 3:
                                        if(i==0)
                                                total+=grid[inputx+1][inputy]+grid[inputx-3][inputy];
                                        if(i==1)
                                                total+=grid[inputx][inputy+1]+grid[inputx][inputy-3];
                                        if(i==2)
                                                total+=grid[inputx+1][inputy+1]+grid[inputx-3][inputy-3];
                                        if(i==3)
                                                total+=grid[inputx+1][inputy-1]+grid[inputx-3][inputy+3];
                                        break;  
                                case 4:
                                        if(i==0)
                                                total+=grid[inputx-4][inputy]+grid[inputx+1][inputy];
                                        if(i==1)
                                                total+=grid[inputx][inputy+1]+grid[inputx][inputy-4];
                                        if(i==2)
                                                total+=grid[inputx-4][inputy-4]+grid[inputx+1][inputy+1];
                                        if(i==3)
                                                total+=grid[inputx-4][inputy+4]+grid[inputx+1][inputy-1];
                                        break;  
                                case 5:
                                        if(i==0)
                                                total+=grid[inputx+4][inputy]+grid[inputx-1][inputy];
                                        if(i==1)
                                                total+=grid[inputx][inputy-1]+grid[inputx][inputy+4];
                                        if(i==2)
                                                total+=grid[inputx+4][inputy+4]+grid[inputx-1][inputy-1];
                                        if(i==3)
                                                total+=grid[inputx+4][inputy-4]+grid[inputx-1][inputy+1];
                                }
                                }
                                if(total==-1 || total==0 || total==-3 || total==-5)
                                return 1;
                        }
                        return 0;
        
}

